﻿#include "stdafx.h"
#include "ListisPalindrome.h"

using namespace std;

namespace algorithm {
bool CListIsPalindrome::Check(ListNode *head)
{
    if (!head) {
        return true;
    }
    // 将链表元素压入栈中
    stack<ListNode*> s;
    ListNode* p = head;
    while (p!= NULL) {
        s.push(p);
        p = p->next;
    }
    p = head;
    while (p!= NULL) {
        if (p == s.top()) {
            // 链表个数奇数，前后依次比较后最终会在中间一个节点相遇
            return true;
        }
        if (p->next == s.top()) {
            // 链表个数偶数，前后依次比较后最终会在中间两个节点相遇，因此比较2个节点值是否相同即可
            return p->val == s.top()->val;
        }
        if (p->val!= s.top()->val) {
            // 值不相同，不是回文链表
            return false;
        }
        // 弹出栈顶元素
        s.pop();
        // 移动到下一个元素
        p = p->next;
    }
    return false;
}
}
